Considering the testability of chips, the overwhelming majority of chips is now set up with scan chains for testing. Since the scan chains are inserted during logic design of chips, and no physical information is included in the insertion, the scan chains in the phase of physical design consequently occupy too many wiring resources and cause wiring congestion or even inability in the wiring. Therefore, it is strictly necessary to structurally optimize the scan chains in the phase of physical design to minimize the wiring resources they may occupy. However, some existing structural optimizations for scan chains focus only on the optimization of one part or a single index, such as time optimization; and these optimal methods are too rough to produce an ideal effect. For instance, they take into account only a lengthwise position or horizontal position of the scanning elements, while excluding the starting and end positions of the scan chains. In addition, a few optimizations in the industry have given global consideration to scanning elements and the positions of scan chains, but they have defects with regard to either optimization efficiency or optimization time.
Thus, to obtain a more effective structural optimization for scan chains has long been a concern in the industry.